The increasing popularity of image applications enables users to leverage use of cameras in mobile devices when performing some tasks. An image application may enable users to capture images on cameras of their mobile devices, which the image application can then submit as queries to perform a search. Typically, the image application evaluates candidate images that are similar to the query submitted to retrieve images that are relevant to the query.
Two types of graphs used to locate images similar to the query are: ε-nearest-neighbor (ε-NN) graph and k-nearest-neighbor (k-NN) graph. These neighborhood graphs are often used in computer vision and machine learning tasks, such as image retrieval, nearest neighbor search, manifold learning and dimension reduction, semi-supervised learning, manifold ranking, and clustering. However, these graphs present challenges in their searches.
For instance, the ε-NN graph includes two nodes that may be connected if their distances are within ε. Basically, the ε-NN graph searches for points that are close to a query point. Limitations of the ε-NN graph include being motivated by geometry and easily resulting in disconnected components. Therefore, the ε-NN graph is not particularly well suited in many applications.
On the other hand, the k-NN graph includes a node that is connected to its k nearest neighbors. The search methods may include an index structure and other search methodologies, such as kd-tree, vantage point tree, spill-tree, or hashing. However, these search methods suffer unfavorable trade-off between complexity of the index structure and accuracy of the search. Research efforts also include constructing an “exact” k-NN graph, which increases the time complexity of every image search. One problem is that the time complexity of the exact k-NN graph construction grows exponentially with respect to a dimension and grows super-linearly with respect to a number. Thus, this makes the exact k-NN graph impractical for high-dimensional data and large scale functions.